Wir haben uns gestern mit dem Halteproblem beschäftigt und sind also zu der Erkenntnis

gekommen, dass es Probleme gibt, die man sehr wohl, sehr sauber spezifizieren kann, aber

zu denen man auch zeigen kann, dass es kein Programm geben kann, das diese Probleme lösen

kann.

Es lässt uns immer noch genügend Platz für interessante Probleme zu lösen, aber auch

unter den Lösbaren müssen wir überlegen, ist es in einer akzeptablen Zeit lösbar?

Und es gibt Probleme, bei denen es besser wäre, wenn sie das Problem lösen wollen und

sie wissen auch wie es geht, nach dem heutigen Stand, dann warten sie ein paar Jahre.

Weil es Probleme gibt, die, wenn ich sie lösen möchte, das vielleicht 100 Jahre dauern

würde mit einem Rechner heutiger Leistung und wenn sie 5 Jahre warten, dann ist der Rechner

plötzlich doppelt so schnell und dann sind sie in 50 Jahren fertig.

Plus 2 Jahre gewartet oder so, dann 52 Jahre.

Also Sie sehen, es ist tatsächlich, es gibt Probleme, die man sehr wohl lösen kann, aber

wenn die Berechnungen exponentiell anwachsen, so schnell anwachsen, dann geht man die gar

nicht erst an, dann ist man mit suboptimalen Lösungen und unter Umständen zufrieden.

Bei dem handlungsreisenden Problem, das ich Ihnen gestern erläutert habe, da hat man zum

Beispiel Algorithmen, also wenn die Kostenfunktion sich sauber verhält, gibt man auch in einer

akzeptablen Zeit eine gute Lösung.

Wenn das nicht ganz der Fall ist, dann hat man zum Beispiel Algorithmen, die einem in

akzeptabler Zeit laufen und garantieren, dass der gefundene Weg maximal doppelt so lang

ist oder so teuer ist, wie der optimale Weg.

Oder es gibt Algorithmen, die einem dann zeigen, dass man in 95% der zugestellten Aufgaben

eine optimale findet und ansonsten etwas länger braucht und so weiter.

Das heißt, die Frage, nicht nur ist es lösbar, sondern wie schnell und wenn ich verschiedene

Algorithmen habe, welcher ist der bessere, der ist sehr wichtig.

In Bezug auf die Komplexität, wir werden uns da nicht sehr ausführlich damit beschäftigen,

aber um dann ein paar Satir-Algorithmen vergleichen zu können, füre ich das ganz kurz ein.

Also wir verstehen unter der Komplexität die maximale Speicher oder Zeitbedarf eines Problems.

Und in der Regel, weil die Hardware im Vergleich billig ist, wenn ich etwas habe, das Zeitbedarf

besser ist, aber mehr Speicher, dann entscheide ich mich in der Regel für das, was schneller

läuft.

Also in der Regel ist es so, dass der Zeitbedarf wichtiger angesehen wird als der Speicherbedarf.

Und um jetzt Algorithmen vergleichen zu können, führen wir so Komplexitätsklassen ein.

Komplexitätsklassen wie das Ganze, der Rechenbedarf steigt linear, der steigt quadratisch, er

steigt exponentiell und wir nehmen dann eine Funktion, die uns sagt, wenn n steigt, wenn

n gegen unendlich geht, wie steigt dann der Rechenzeitbedarf?

Das ist diese Funktion, die kann wie gesagt exponentiell sein, dann wäre es a hoch n,

sie kann polynomial sein, dann wäre es n hoch 2, 3, 4, was immer, sie kann linear sein,

n hoch 1 oder sie kann konstant sein.

Und wir schauen dann, wie sich diese Funktion verhält und geben dann, sagen dann o von und

fassen dann zum Beispiel alle, die quadratisch wachsen, zusammen mit o von n².

Und ob da jetzt noch irgendwelche linearen Terme oder konstanten Terme mit dabei sind,

das interessiert uns nicht, uns interessiert nur, was passiert, wenn wir gegen sehr große

Werte gehen.

Also das Anwachsen des Aufwands beim Vergrößern des Problems.

Ja, und hier ein paar Beispiele, damit haben wir gestern aufgehört, also wir sehen hier

x gleich x plus 1, es gibt da gar kein n, das ist konstant, das heißt, das ist o von

Hier wir sehen, das was in der Schleife passiert, muss n mal durchgeführt werden, somit ist

das die Komplexität o von n.